The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices. However, even today's most sophisticated computer systems continue to include many of the basic elements that were present in some of the first computer systems. One such element is the computer system's processor. A computer system's processor is the intelligent portion of the computer system. The processor is responsible for executing programs that interpret and manipulate information that is given to the computer system by the computer system's user or users.
As is well known, the processor operates on data contained within its registers with greater speed than operations on data stored external to the processor (i.e., in main memory). Designers of processors choose the number of processor registers which will allow the processor to perform well. The number of processor registers in a typical computer system is relatively small compared to the number of program variables in a typical computer program that the processor executes. Thus, the many program variables in a computer program must be allocated to specific processor registers for the processor to appropriately operate on the data.
Each of the program variables that are operated upon in a computer program must be assigned a corresponding processor register. Allocating the fixed number of processor registers to a much larger number of program variables in a computer program is generally referred to as register allocation. The performance of the computer system depends on how efficiently the processor uses its registers, which depends on the efficiency of the register allocation scheme. Therefore, register allocation is critical to the performance of the computer system. One common device that allocates program variables in the computer program to processor registers is commonly referred to as a compiler. Register allocation in a typical compiler uses the concept of "live ranges" or "lifetimes" of program variables. The "live range" or "lifetime" of a particular program variable is the span of instructions for which the variable contains valid data, and may be computed in a number of different ways.
One common method of allocating registers in a computer system constructs an interference graph of all live ranges in an instruction stream, then colors the graph with a number of colors corresponding to the number of processor registers. As discussed in the related applications cited above, there are many different schemes for coloring an interference graph. If a live range in the interference graph cannot be colored, it must be "spilled," meaning that the variable must be stored in memory rather than keeping its value in a register. Since the processor can only operate on data stored in registers, spilling a live range implies that the value must be loaded from memory into a register when it is needed, and stored back to memory when changed.
Spilling a live range requires the insertion of instructions into the instruction stream to perform the necessary stores to memory and loads from memory. These instructions are known as "spill code." The generation of spill code requires compiler time, and the presence of spill code in the instruction stream reduces the performance of the computer program. For these reasons, the generation of spill code must be done in an efficient manner to enhance the compile time of the instruction stream. In addition, the amount of spill code should be minimized to assure the best performance of the resultant machine code instruction stream.
Many known methods of generating spill code generate more spill code than is needed (reducing the performance of the resultant machine code instruction stream), or generate the spill code in an inefficient manner (increasing the compile time). Without methods and apparatus for improving the efficiency of spill code generation in compilers, excessive compile time and excessive spill code will continue to be an impediment to the overall performance of a computer system.